#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
// 环形子数组的最大和：https://leetcode.cn/problems/maximum-sum-circular-subarray/description/
using namespace std;
class Solution {
public:
    //将本题转换后即等价于最大子数组和
    const int INF=0x3f3f3f3f;
    int maxSubarraySumCircular(vector<int>& nums) {
        int sum=0,n=nums.size();
        for(auto x:nums) sum+=x;
        vector<int> f(n+1,-INF);
        vector<int> g(n+1,INF);
        int ret1=-INF,ret2=INF;
        for(int i=1;i<=n;i++)
        {
            f[i]=max(nums[i-1],nums[i-1]+f[i-1]);
            g[i]=min(nums[i-1],nums[i-1]+g[i-1]);
            ret1=max(f[i],ret1);
            ret2=min(g[i],ret2);
        }  
        //如果整个数组都是负数，那么sum-ret2=0，而ret1<0,这显然不是我们想要的
        return ret2==sum?ret1:max(ret1,sum-ret2);  
    }
};